package com.njupt.Tree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author: wujiaming
 * @CreateTime: 2024/12/9 16:58
 * @Description: 538. 把二叉搜索树转换为累加树
 * @Version: 1.0
 */


public class ConvertBST {

    private TreeNode root = null;

    private int sum = 0;

    /**
     * 构造一一颗新树，先序递归遍历这颗树
     * 对于当前遍历的值，寻找树中比其大的值的和
     * 然后分别构建右左子树
     * @param root
     * @return
     */
    public TreeNode convertBST1(TreeNode root) {
        this.root = root;
        return convert(root);
    }

    public TreeNode convert(TreeNode root){
        if(root == null){
            return null;
        }
        int val = calSum(this.root,root.val);
        TreeNode rootNode = new TreeNode(val);
        rootNode.left = convert(root.left);
        rootNode.right = convert(root.right);
        return rootNode;
    }

    private int calSum(TreeNode root, int val) {
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        int sum = 0;
        while(cur != null || !stack.isEmpty()){
            if(cur != null){
                //访问节点
                if(cur.val>=val){
                    sum += cur.val;
                }

                stack.push(cur);
                cur = cur.left;
            }else {
                cur = stack.pop();
                cur = cur.right;
            }
        }
        return sum;
    }


    /**
     * 法二：
     * 这里还有一个重要的条件，那就是这棵树本来就是一颗二叉搜索树，是有序的
     * 可以采用右根左的顺序进行遍历
     * @param root
     * @return
     */
    public TreeNode convertBST(TreeNode root) {
        traverse(root);
        return root;
    }

    private void traverse(TreeNode root) {

        if(root == null){
            return;
        }
        traverse(root.right);
        root.val += this.sum;
        this.sum = root.val;
        traverse(root.left);
    }




    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(1);
        root.right = new TreeNode(6);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(2);
        root.left.right.right = new TreeNode(3);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(7);
        root.right.right.right = new TreeNode(8);
        ConvertBST test = new ConvertBST();
        long start = System.currentTimeMillis();
        TreeNode root1 = test.convertBST(root);
        long end = System.currentTimeMillis();
        System.out.println(end-start);
        System.out.println();

    }
}
